def makeCombi(n, k):
ans = []
tmp = []
def makeCombiUtil(n, left, k):
if (k == 0):
ans.append(tmp[:])
return
for i in range(left, n + 1):
tmp.append(i)
makeCombiUtil(n, i + 1, k - 1)
tmp.pop()
makeCombiUtil(n, 1, k)
return ans
def fun(cmb, arr, b, s):
sum = 0
tempArr = []
for i in cmb:
tempArr.append(s[i-1])
l = 0
for i in range(len(arr)):
if arr[i] == b[i] or arr[i] in tempArr:
l += 1
else:
sum += (l * (l+1)) // 2
l = 0
return sum + (l * (l+1)) // 2
def f(n, k, a, b):
s = set()
for i in range(n):
if a[i] != b[i]:
s.add(a[i])
s = list(s)
if len(s) <= k:
return (n * (n + 1)) // 2
combArr = makeCombi(len(s), k)
mxm = 0
for cmb in combArr:
mxm = max(mxm, fun(cmb, a, b, s))
return mxm
for _ in range(int(input())):
n, k = map(int, input().split())
a = input().strip()
b = input().strip()
print(f(n, k, a, b))
#include <bits/stdc++.h>
#define forr(i,a,b) for(int i=(a);i<(b);i++)
#define forn(i,n) forr(i,0,n)
#define dforn(i,n) for(int i=n-1;i>=0;i--)
#define forall(it,v) for(auto it=v.begin();it!=v.end();it++)
#define sz(c) ((int)c.size())
#define rsz resize
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fst first
#define snd second
#ifdef ANARAP
//local
#else
//judge
#endif
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
map<char,int> m;
string a,b;
int n,k;
const int inf = 1e7;
int main() {
#ifdef NANO
freopen("input.in", "r", stdin);
//freopen("output.out","w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t--){
cin>>n>>k;
cin>>a>>b;
set <char> aux;
for(auto e: a) aux.insert(e);
int id = 0;
m.clear();
for(auto e: aux) m[e] = id, id++;
long long ans = 0;
for(int mask = 0; mask<(1<<((int) aux.size()+1)); mask++){
if(__builtin_popcount(mask) <= k){
long long l = 0;
long long auxx = 0;
forn(i,n){
int idx = m[a[i]];
if(a[i] == b[i] or ((1<<idx)&mask)){
auxx += (i-l+1);
}
else l = i+1;
}
ans = max(ans,auxx);
}
}
cout<<ans<<'\n';
}
return 0;
}
231A - Team | 479C - Exams |
1030A - In Search of an Easy Problem | 158A - Next Round |
71A - Way Too Long Words | 160A - Twins |
1A - Theatre Square | 1614B - Divan and a New Project |
791A - Bear and Big Brother | 1452A - Robot Program |
344A - Magnets | 96A - Football |
702B - Powers of Two | 1036A - Function Height |
443A - Anton and Letters | 1478B - Nezzar and Lucky Number |
228A - Is your horseshoe on the other hoof | 122A - Lucky Division |
1611C - Polycarp Recovers the Permutation | 432A - Choosing Teams |
758A - Holiday Of Equality | 1650C - Weight of the System of Nested Segments |
1097A - Gennady and a Card Game | 248A - Cupboards |
1641A - Great Sequence | 1537A - Arithmetic Array |
1370A - Maximum GCD | 149A - Business trip |
34A - Reconnaissance 2 | 59A - Word |